package stack;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * Created by IntelliJ IDEA.
 * User: 杰哥
 * Date: 2020/3/29
 * Time: 12:29
 */
public class PolandNotation  {
    public static void main(String[] args) {
       /* String suffixExpression = "30 4 + 5 * 6 -"; //(30+4)*5-6的逆波兰表达式
        List<String> listString = getListString(suffixExpression);
        int calculate = calculate(listString);
        System.out.println(calculate);*/
        String expression = "1+((2+3)*4)-5"; //1.书写中缀表达式
        List<String> list = toInfixExpressionList(expression); //2.将其转换成对应的List
        List<String> suffixList = parseSuffixExpressionList(list); //3.再转换为后缀表达式对应的List
        int calculate = calculate(suffixList); //4.对后缀表达式对应的List作为参数进行计算，得到结果
        System.out.println(expression+"="+calculate);

    }

    public static List<String> getListString(String suffixExpression) {
        String[] split = suffixExpression.split(" ");
        List<String> list = Arrays.asList(split);
        return list;
    }

    /**
     * 对后缀表达式对应的List进行计算
     * @param ls
     * @return
     */
    public static int calculate(List<String> ls) {
        Stack<String> stack = new Stack<String>();
        for (String item : ls) {
            if(item.matches("\\d+")) { //匹配多位数
                stack.push(item);
            }else {
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = 0;
                if(item.equals("+")) {
                    res = num1 + num2;
                }else if (item.equals("-")) {
                    res = num1 - num2;
                }else if (item.equals("*")) {
                    res = num1 * num2;
                }else if (item.equals("/")) {
                    res = num1 / num2;
                }else {
                    throw new RuntimeException("运算符有误！");
                }
                stack.push(res+"");
            }
        }
        return Integer.parseInt(stack.pop());
    }

    /**
     * 将中缀表达式转对应的List
     */
    public static List<String> toInfixExpressionList(String s) {
        List<String> ls = new ArrayList<String>();
        int len = s.length();
        char c = 0;
        int i = 0;
        String str = "";

        while (i < len) {
            if((c = s.charAt(i)) < 48 || c > 57  ) { //如果c是一个非数字
                ls.add(c+"");
                i++;
            }else {
                str = "";
                while (i < len && (c = s.charAt(i)) >= 48 && c <= 57) {
                    str += c;
                    i++;
                }
                ls.add(str);
            }
        }
        return ls;
    }

    /**
     * 中缀表达式对应的List转后缀表达式对应的List
     */
    public static List<String> parseSuffixExpressionList(List<String> ls) {
        //定义两个栈
        Stack<String> s1 = new Stack<String>(); //符合栈
        //↓因为s2这个栈转换过程中没有pop操作，而且 后面还需逆序输出，比较麻烦，所有这里可直接使用List<String>
        List<String> s2 = new ArrayList<String>();
        for (String item : ls) {
            if(item.matches("\\d+")) { //如果是一个数
                s2.add(item);
            }else  if(item.equals("(")) {
                s1.push(item);
            }else if(item.equals(")")) { // 如果是右括号
                while (!s1.peek().equals("(")) {  //依次弹出s1栈顶的运算符并压入s2,直到遇到左括号为止
                    s2.add(s1.pop());
                }
                s1.pop(); //此时将这一对括号丢弃
            }else {
                //当item的优先级小于等于s1栈顶运算符优先级，将s1栈顶栈顶的运算符弹出并加入到s2中
                while (s1.size() != 0 &&  priority(s1.peek()) >= priority(item)) {
                    s2.add(s1.pop());
                }
                s1.push(item);
            }
        }
        //将s1中剩余的运算符依次弹出加入到s2
        while (s1.size() > 0) {
            s2.add(s1.pop());
        }
        return s2;

    }

    /**
     * 返回运算符的优先级
     * @param operation 运算符
     * @return
     */
    public static int priority(String operation) {
        if(operation.equals("*")  || operation.equals("/")) {
            return 2;
        }else if(operation.equals("+") || operation.equals("-")) {
            return 1;
        }
        return 0;
    }
}


